/**
 * 1138. 字母板上的路径
 * https://leetcode-cn.com/problems/alphabet-board-path/
 */
public class Solutions_1138 {
    public static void main(String[] args) {
//        String target = "zb";  // output: "DDDDD!UUUUUR!"
//        String target = "leet";  // output: "DDR!UURRR!!DDD!"
        String target = "code";  // output: "RR!DDRR!UUL!R!"

        String result = alphabetBoardPath(target);
        System.out.println(result);
    }

    public static String alphabetBoardPath(String target) {
//        String[] board = {"abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"};
        StringBuilder sb = new StringBuilder();
//        StringBuilder show = new StringBuilder();
        int x = 0, y = 0;
        for (int i = 0; i < target.length(); i++) {
            char c = target.charAt(i);
            // 计算出要到达的行和列
            int toY = (c - 'a') / 5;
            int toX = (c - 'a') % 5;
            // 因为 'z' 的存在，需要先向左移动，才能向下边移动，即先 'L' 再 'D'
            // 需要先向上移动，才能向右移动，即先 'U' 再 'R'
            // 去左边
            while (x > toX) {
                x --;
                sb.append("L");
            }
            // 去下边
            while (y < toY) {
                y ++;
                sb.append("D");
            }
            // 去上边
            while (y > toY) {
                y --;
                sb.append("U");
            }
            // 去右边
            while (x < toX) {
                x ++;
                sb.append("R");
            }
//            show.append(board[toY].charAt(toX));
            sb.append("!");
        }
        return sb.toString();
    }
}
